package uba.fi.tda.tp3;

public class ColaPrioridad {

	private Comparable datos[];

	private int heap_size;

	private int max_heap_size;

	public boolean vacia() {
		if (heap_size == 0)
			return true;
		else
			return false;

	}

	public ColaPrioridad(int _max_heap_size) {
		max_heap_size = _max_heap_size;
		datos = new Comparable[max_heap_size];
	}

	public void encolar(Comparable nuevo) {
		if (heap_size < max_heap_size) {

			datos[heap_size] = nuevo;
			int i = heap_size;
			while (i > 0 && ((datos[i].compareTo(datos[(i - 1) / 2])) == -1)) {
				int padre = (i - 1) / 2;
				Comparable aux = datos[i];
				datos[i] = datos[padre];
				datos[padre] = aux;
				i = padre;
			}
			heap_size++;
		}
	}

	public Comparable extraerMinimo() {

		Comparable temp;
		if (heap_size < 1)
			return null;
		temp = datos[0];
		datos[0] = datos[heap_size - 1];
		heap_size--;
		crear_heap(0, heap_size);
		return temp;
	}

	private void crear_heap(int inf, int sup) {

		int hijo = 0;
		Comparable tmp;

		if (2 * (inf + 1) - 1 >= sup)
			return;
		// Se procesa el menor de los hijos.
		hijo = 2 * (inf + 1) - 1;
		if (2 * (inf + 1) < sup) {
			if ((datos[2 * (inf + 1)]).compareTo(datos[2 * (inf + 1) - 1]) == -1)
				hijo = 2 * (inf + 1);
		}

		if (datos[inf].compareTo(datos[hijo]) == 1) {
			tmp = datos[inf];
			datos[inf] = datos[hijo];
			datos[hijo] = tmp;
			crear_heap(hijo, sup);
		}
	}
}

